/**
 * 剑指 Offer 11. 旋转数组的最小数字（与 153，154 同）
 * https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/
 */
public class Solutions_Offer_11 {
    public static void main(String[] args) {
        int[] nums = {3, 4, 5, 1, 2};  // output: 1
//        int[] nums = {2, 2, 2, 0, 1};  // output: 0
//        int[] nums = {3, 3, 1, 3};  // output: 1
//        int[] nums = {3, 1, 1, 1, 1};  // output: 1
//        int[] nums = {1, 3, 5};  // output: 1

        int result = minArray(nums);
        System.out.println(result);
    }

    /**
     * 二分查找法
     * 为什么要将 mid 与 right 进行比较？
     * 例如：将 {1, 2, 2, 3, 4, 5, 6, 7} 翻转成 {2, 3, 4, 5, 6, 7, 1, 2} 后，查找最小值
     * 第 1 次二分中间点为 5，此时 5 大于 right 索引上的 2，那么可以肯定 5 后面的元素
     * 起码有一部分是翻转过来的，因为数组是升序排列的
     * 而将 5 与 left 索引上的值比较时，不能得到准确的信息
     */
    public static int minArray(int[] numbers) {
        if (numbers == null || numbers.length < 1) {
            // 没有元素
            return -1;
        }
        int left = 0, right = numbers.length - 1;
        while (left <= right) {
            // 中间索引
            int mid = left + (right - left) / 2;
            if (numbers[mid] == numbers[right]) {
                // 去除右侧的重复元素
                right --;
            } else if (numbers[mid] > numbers[right]) {
                // 说明数组旋转了，且最小元素一定在 mid 右侧，舍弃 mid 及 mid 左侧元素
                left = mid + 1;
            } else {
                // mid 右侧的都是较大的元素，舍弃 mid 右侧元素，继续检索 [left, mid] 区间的元素
                right = mid;
            }
        }
        // 最终 left 索引上的元素一定是最小元素
        return numbers[left];
    }

    /**
     * 线性扫描法
     */
    public static int minArray2(int[] numbers) {
        if (numbers == null || numbers.length < 1) {
            // 没有元素
            return -1;
        }
        for (int i = 0; i < numbers.length - 1; i++) {
            if (numbers[i] > numbers[i + 1]) {
                // 翻转了，最小的元素就是翻转后的元素
                return numbers[i + 1];
            }
        }
        // 未翻转的情况下，第一个元素，即是最小的元素
        return numbers[0];
    }
}
